// https://leetcode.cn/problems/word-pattern/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        int m = pattern.size();
        int n = s.size();

        unordered_map<char, string> p2s;
        unordered_map<string, char> s2p;

        int i = 0;
        int j = 0;
        for (int k = 0; k < n; k++) {
            if (s[k] == ' ' || k == n - 1) {
                string word;
                if (k == n - 1) {
                    word = s.substr(j);
                } else {
                    word = s.substr(j, k - j);
                }
                
                if (p2s.count(pattern[i]) && p2s[pattern[i]] != word) {
                    return false;
                }
                if (s2p.count(word) && s2p[word] != pattern[i]) {
                    return false;
                }

                p2s[pattern[i]] = word;
                s2p[word] = pattern[i];

                i++;
                j = k + 1;
            }
        }
        return i == m;
    }
};